package leetcode.day_2020_2021_2_1_2021_2_7;

import java.util.*;

/**
 * 30. 串联所有单词的子串
 * https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
 * https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-6/
 */
public class LeetCode0030 {
    public static void main(String[] args) {
        System.out.println(findSubstring("barfoothefoobarma", new String[]{"foo","bar"}));
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (words.length == 0) return res;
        // words单词的个数
        int count = words.length;
        // words中所有单词拼接的长度
        int wordLen = words[0].length();
        // 获取words中单词的个数并保存在map中
        Map<String, Integer> wordCountMap = new HashMap<>();
        for (String word : words) {
            wordCountMap.put(word, wordCountMap.getOrDefault(word, 0)+1);
        }

        // 遍历所有子串
        for(int i=0; i<s.length() - count*wordLen+1; i++) {
            // curMap存放扫描的单词及其出现的次数
            Map<String, Integer> curMap = new HashMap<>();
            int num = 0;
            // 判断该子串是否否和
            while (num < count) {
                String word = s.substring(i+num*wordLen, i+(num+1)*wordLen);
                if (wordCountMap.containsKey(word)) {
                    curMap.put(word, curMap.getOrDefault(word, 0)+1);
                    if (wordCountMap.get(word) < curMap.get(word)) break;
                } else {
                    break;
                }
                num ++;
            }
            if (num == count) res.add(i);
        }
        return res;
    }
}
